package LeetCode.LeetCode2;

/**
 * 删除链表倒数第K个节点
 * @author lumin
 * @date 2022/03/17 13:33
 **/
public class Num19 {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    //快慢指针,快指针先走k步,然后一起走,当快指针走到链表末尾的时候,慢指针的下一个节点刚好是要删除的节点
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null){
            return null;
        }
        if(head.next == null && n == 1){
            return null;
        }
        ListNode dummyHead = new ListNode(0,head);
        ListNode fast = head;
        ListNode low = dummyHead;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        while(fast != null){
            fast = fast.next;
            low = low.next;
        }
        //此时low指向节点的下一个就是要删除的节点
        low.next = low.next.next;
        return dummyHead.next;
    }
}